package 动态规划;

public class 动态规划算法_最大字段和 {

    public static int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] leftMax = new int[n];
        leftMax[0] = nums[0];
        int leftSum = nums[0];
        int pre = leftSum, res = leftSum;
        for (int i = 1; i < n; i++) {
            //可能只在左边
            pre = Math.max(pre + nums[i], nums[i]);
            res = Math.max(res, pre);
        }
        return res;
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = {-6, -2, -1, 5, -2};
        System.out.println(maxSubArray(a));
    }
}